/*
 *  Optimized version of Quick sort:
 *  1. shuffle first
 *  2. cut off to insertion sort
 *  3. median3
 */
package algs4.sort;

public class QuickX
{
    /* Fields */
    private static final int CUTOFF_SIZE = 8;

    /* Static Methods */
    public static void sort(Comparable[] a) {
        // shuffle?
        sort(a, 0, a.length - 1);
    }

    public static void sort(Comparable[] a, int st, int ed) {
        // base case
        if (ed < st + CUTOFF_SIZE) {
            insertionSort(a, st, ed);
            return;
        }

        int k = partition(a, st, ed);

        sort(a, st, k - 1);
        sort(a, k + 1, ed);
    }

    private static int partition(Comparable[] a, int st, int ed) {
        int i = st;
        int j = ed;
        int m = median3(a, st, (st + ed) / 2, ed);

        Comparable v = a[m];

        a[m] = a[st];  // swap a[st] and a[m]

        while (i < j) {
            while (i < j && a[j].compareTo(v) >= 0) j--;
            a[i] = a[j];

            while (i < j && a[i].compareTo(v) <= 0) i++;
            a[j] = a[i];
        }

        a[i] = v;

        return i;
    }

    /* private static int partition(Comparable[] a, int st, int ed) {
        int i = st;
        int j = ed + 1;
        int m = median3(a, st, (st + ed) / 2, ed);

        Comparable v = a[m];

        // swap a[st] and a[m]
        a[m]  = a[st];
        a[st] = v;

        // a[st] is unique largest element
        while (a[++i].compareTo(v) < 0) {
            if (i == ed) { exch(a, st, ed); return ed; }
        }

        while (a[--j].compareTo(v) > 0) {
            if (j == st + 1) return st;
        }

        while (i < j) {
            exch(a, i, j);

            while (a[++i].compareTo(v) < 0);
            while (a[--j].compareTo(v) > 0);
        }

        exch(a, st, j);

        return j;
    } */

    private static void exch(Object[] a, int p, int q) {
        Object v = a[p];

        a[p] = a[q];
        a[q] = v;
    }

    // insertion sort for cutoff
    private static void insertionSort(Comparable[] a, int st, int ed) {
        for (int i = st + 1; i <= ed; i++) {
            int        j = i;
            Comparable v = a[i];

            for (; j > st && v.compareTo(a[j-1]) < 0; j--)
                a[j] = a[j-1];

            a[j] = v;
        }
    }

    private static int median3(Comparable[] a, int i, int j, int k) {
        return (a[i].compareTo(a[j]) > 0 ?
               (a[j].compareTo(a[k]) > 0 ? j : a[i].compareTo(a[k]) > 0 ? k : i) :
               (a[j].compareTo(a[k]) < 0 ? j : a[i].compareTo(a[k]) < 0 ? k : i));
    }
}
